package 面试代码;

import java.util.LinkedHashMap;

/**
 * @author zx
 * @create 2022-08-23 17:12
 * 点赞最多的题解,确实讲的清楚：
 * https://leetcode.cn/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
 *
 * 1.为什么必须要用双向链表：因为删除操作,删除一个节点不光要得到该节点本身的指针,也需要操作其前驱节点的指针
 * 而双向链表才能支持直接查找前驱,保证操作的时间复杂度 O(1)
 *
 * 2.为什么要在链表中同时存储key和val,而不是只存储val：
 * 注意makeRecently函数中,需要用deletedNode得到deletedKey也就是说,当缓存容量已满,
 * 不仅仅要删除最后一个Node节点,还要把map中映射到该节点的key同时删除
 * 而这个key只能由Node得到.如果Node结构中只存储val,那么就无法得知key是什么,就无法删除map中的键,造成错误
 *
 */

/**
 * 面试写这个
 */
public class LRUCache {
    private int capacity;
    //key：val    value：val ----  重点注释

    //每次默认从链表尾部添加元素,尾部的元素就是最近使用的,头部的元素就是最久未使用的
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    /**
     * @return 获取元素的方法
     */
    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        makeRecently(key);
        return cache.get(key);
    }

    /**
     * @return 添加元素的方法
     */
    public void put(int key, int value) {
        //key已存在
        if(cache.containsKey(key)){
            cache.put(key,value);
        }else{//key不存在,需要添加
            if(cache.size() == capacity){//容量已满
                //淘汰最久未使用的：链表头部就是最久未使用的key
                //找到链表头部的key
                int oldestKey = cache.keySet().iterator().next();
                //容量未满,则将新的key添加链表尾部
                cache.remove(oldestKey);
            }else{
                //放到下面显得代码不冗余
            }
            cache.put(key,value);
        }
        //将key变为最近使用
        makeRecently(key);
    }

    /**
     *
     * @return 将一个元素变为最近使用的元素
     */
    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key,重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}
